package cn.cxq.learning.recursion;

import org.junit.jupiter.api.Test;

public class LongestIncrease {
    int max = 0;
    boolean[][] visited;

    @Test
    public void test() {
        solve(new int[][]{{1,2,3},{4,5,6},{7,8,9}});
    }

    public int solve (int[][] matrix) {
        // write code here
        visited = new boolean[matrix.length][matrix[0].length];

        dfs(matrix, 0, 0, 1);

        return max;
    }

    private void dfs (int[][] matrix, int x, int y, int dis) {

        if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length) { // 越界即停
            return;
        }

        if (x == matrix.length - 1 && y == matrix[0].length - 1) { // 到终点就停下
            if (dis > max) { // 刷新max
                max = dis;
            }
            return;
        }

        if (!visited[x][y]) {
            visited[x][y] = true;
            dfs(matrix, x - 1, y, dis + 1); //上
            dfs(matrix, x + 1, y, dis + 1); //下
            dfs(matrix, x, y - 1, dis + 1); //左
            dfs(matrix, x, y + 1, dis + 1); //右
            visited[x][y] = false;
        }
    }
}
